package leetcode.editor.cn.dsa26_unionfind;

/**
 * 并查集
 */
public class UnionFindSet {
    /**
     * parent[]存储每个节点的父节点，路径压缩之后，存储代表节点/元
     * 哈希表存储结构： key：节点； value：父节点（或代表节点）
     * 将节点坐标封装后作为parent的索引，对应的值为集合代表节点
     * 格式如：parent[节点] = 父节点;
     */
    private int[] parent;
    /**
     * rank[]按理说应存储每个子集的层次（秩），这里简单存储为每个集合的元素个数
     * 哈希表存储结构： key：根节点； value：节点个数
     * 将根节点坐标封装后作为rank的索引，对应的值为集合节点个数
     * 格式如： rank[根节点] = 节点个数;
     */
    private int[] rank;
    // 小集合的个数
    private int count;

    /**
     * 获取并查集中集合的个数
     * @return
     */
    public int getCount() {
        return count;
    }

    /**
     * 初始化：
     * 把每个元素所在集合初始化为其自身
     * 集合的秩为1
     * @param grid
     */
    public UnionFindSet(char[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        parent = new int[m * n];
        rank = new int[m * n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    int value = hash(i, j, n);
                    parent[value] = value;
                    rank[value] = 1;
                    ++count; // 小集合的数量+1
                }
            }
        }
    }

    /**
     * 将二维数组的数组转换为一维数组的坐标
     * 转换公式： index = i * n + j（n = grid[0].length）
     * 还原公式： i = index / n， j = index % n
     */
    public int hash(int i, int j, int n) {
        return i * n + j;
    }

    /**
     * 查询元素所在的集合，返回该集合的代表元（代表节点）
     * 路径压缩：将所有节点（包括根节点）的父节点都设置为根节点
     * 复杂度：下一次查找效率为： O(1)
     * 递归实现步骤：
     * 判断当前节点的父节点（即代表节点）是否与自己相同
     * 索引与值相同，意味着该节点的父节点就是自己，即找到了当前集合的代表节点
     * 反之，递归地查找父节点的父节点，并将其结果作为当前节点的父节点
     * 最终，每个节点的父节点都将直接指向代表节点，形成一个菊花图
     * @param i
     * @return
     */
    public int find(int i) {
        // 循环/递归地向上查找父节点，直到找到代表节点
        // 对于路径中非代表节点要进行路径压缩
        if(parent[i] != i) {
            parent[i] = find(parent[i]);
        }
        return parent[i];
    }

    /**
     * 合并两个节点
     * 1.分别获取两个节点的代表节点
     * 2.不属于同一个集合，才进行合并
     * 3.集合合并，数量减 1
     * @param x
     * @param y
     */
    public void union(int x, int y) {
        // 1.分别获取两个节点的代表节点
        int rootX = find(x);
        int rootY = find(y);
        // 2.不属于同一个集合，才进行合并
        // 将层次少的集合的根节点的父节点指向层次多的集合的根节点
        if (rootX != rootY) {
            if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else if (rank[rootX] > rank[rootY]) {
                parent[rootX] = rootY;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
            // 3.集合合并，数量减 1
            count--;
        }
    }
}
